package GreedyAlgorithmPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class canCompleteCircuit_ {

  public int canCompleteCircuit(int[] gas, int[] cost) {
    int curSum = 0; // 记录i油差
    int totalSum = 0; // 记录总油差
    int start = 0;
    for (int i = 0 ; i < gas.length ; i ++){
      curSum += (gas[i] - cost[i]);
      totalSum += (gas[i] - cost[i]);
      if (curSum < 0){
        start = i + 1;
        curSum = 0;
      }
    }
    if (totalSum < 0){
      return -1;
    }
    return start;
  }
}
